#lang sicp

;; binary tree
(define (make-tree)
  (define tree nil)
  (define compare (lambda (a b) (- a b)))

  (define (make-node key value) (list key value))
  (define (key-node node) (car node))
  (define (value-node node) (cadr node))
  (define (set-value-node! node value) (set-car! (cdr node) value))

  (define (make-tree l n r) (list l n r))
  (define (left-branch tree) (car tree))
  (define (right-branch tree) (caddr tree))
  (define (node-tree tree) (cadr tree))
  (define (set-left-branch! tree b) (set-car! tree b))
  (define (set-right-branch! tree b) (set-car! (cddr tree) b))
  

  (define (search key)
    (define (iter tree)
      (cond ((null? tree) #F)
            ((> (compare (key-node (node-tree tree)) key) 0)
             (iter (left-branch tree)))
            ((< (compare (key-node (node-tree tree)) key) 0)
             (iter (right-branch tree)))
            (else
             (value-node (node-tree tree)))))
    (iter tree))

  (define (insert! key value)
    (define (iter tree)
      (cond ((> (compare (key-node (node-tree tree)) key) 0)
             (let ((left (left-branch tree)))
               (if (null? left)
                   (set-left-branch! tree (make-tree nil (make-node key value) nil))
                   (iter left))))
            ((< (compare (key-node (node-tree tree)) key) 0)
             (let ((right (right-branch tree)))
               (if (null? right)
                   (set-right-branch! tree (make-tree nil (make-node key value) nil))
                   (iter right))))
            (else (set-value-node! (node-tree tree) value))))
    (if (null? tree)
        (set! tree (make-tree nil (make-node key value) nil))
        (iter tree)))

  (define (count-node)
    (define (iter tree)
      (if (null? tree)
          0
          (+ 1
             (iter (left-branch tree))
             (iter (right-branch tree)))))
    (iter tree))


  (define (display-tree)
    (define count (count-node))
    tree)
             
  
  (define (dispatch m)
    (cond ((eq? m 'search-proc) search)
          ((eq? m 'insert!-proc) insert!)
          ((eq? m 'count) (count-node))
          ((eq? m 'tree) tree)
          (else
           (error ""))))
  dispatch)



(define tree (make-tree))

(define search (tree 'search-proc))
(define insert! (tree 'insert!-proc))


(insert! 10 'first)
(insert! 15 'second)
(insert! 4 'third)
(insert! 1 'fourth)
(insert! 8 'fifth)
(insert! 20 'sixth)
(insert! 11 'seventh)
(insert! 18 'eighth)